package com.arithmeticEveryDay.luoguOJ;

import java.util.Scanner;

/*
TODO：这题我写在蓝桥包下了，这里的做法状态不好记录，应该把row直接换成本行的摆放状态status的
在N×N 的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。
国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

输入格式
只有一行，包含两个数N, K。


101 100 100 100 100 010 010 010 001 001 001 001 000 000 000 000
000 001 000 000 000 000 000 000 100 000 000 000 101 100 001 000
000 000 100 010 001 100 010 001 000 100 010 001 000 001 100 101

状态记录：

3 2
16
 */
public class MainP1896 {

    int n;
    int k;
    int[] board;

    public MainP1896(int n, int k) {
        this.n = n;
        this.k = k;
        board = new int[n];
    }

    public int dfs(int count, int row, int col) {
        int result = 0;
        if (count == k) {
            return 1;
        }
        if (row >= n || col >= n) {
            return 0;
        }
        if (isOK(board, row, col)) {
            int temp = board[row];
            board[row] = board[row] ^ (1 << (n-1-col));
            if (col < n-1) {
                result += dfs(count+1, row, col+1);
            } else {
                result += dfs(count+1, row+1, 0);
            }
            board[row] = temp;
        }
        if (col < n-1) {
            result += dfs(count, row, col+1);
        } else {
            result += dfs(count, row+1, 0);
        }
        return result;
    }

    private boolean isOK(int[] board, int row, int col) {
        int left = (board[row] >> (n-col)) % 2;
        if (left == 1) {
            return false;
        }
        if (row > 0) {
            int upleft = board[row-1] >> (n-col);
            int up = board[row-1] >> (n-col-1);
            int upright = board[row-1] >> (n-col-2);
            if (upleft % 2 == 1 || up % 2 == 1 || upright % 2 == 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        MainP1896 m = new MainP1896(n, k);
        /*
        // isOK测试
        int[] board = {1, 16};
        System.out.println(m.isOK(board, 1, 1));
        System.out.println(m.isOK(board, 2, 1));
        System.out.println(m.isOK(board, 3, 1));
        */
        System.out.println(m.dfs(0, 0, 0));
    }

}
